/* 链式队列定义 */
typedef Vertex QElemSet;
#define NIL -1

typedef struct QueueNode *QPosition; /* 指针即结点位置 */
struct QueueNode {
    QElemSet data; /* 存储数据 */
    QPosition next; /* 链接队列中下一个元素的位置 */
};
typedef struct QueueHeadNode *Queue;
struct QueueHeadNode {
    int size; /* 链接队列中当前元素个数 */
    QPosition front; /* 链接队列的队首指针，初始化为NULL */
    QPosition rear; /* 链接队列的队尾指针，初始化为NULL */
};

void InitQueue(Queue queue) {
    /* 初始化一个空的链接队列 */
    queue->size = 0;
    queue->front = NULL;
    queue->rear = NULL;
}

bool IsEmpty(Queue queue) {
    /* 判断队列是否为空 */
    if (queue->size == 0)
        return true;
    else
        return false;
}

void EnQueue(Queue queue, QElemSet x) {
    QPosition new_node;

    new_node = (QPosition)malloc(sizeof(struct QueueNode));
    new_node->data = x;
    new_node->next = NULL;
    if (IsEmpty(queue)) { /* 特殊处理插入空队列的情况 */
        queue->rear = new_node;
        queue->front = new_node;
    } else {
        queue->rear->next = new_node;
        queue->rear = queue->rear->next;
    }
    queue->size++;
}

QElemSet GetFront(Queue queue) {
    if (IsEmpty(queue)) {
        printf("错误：队列为空。\n");
        return NIL;
    } else {
        return queue->front->data;
    }
}

void DeQueue(Queue queue) {
    QPosition temp;

    if (IsEmpty(queue)) {
        printf("错误：队列为空。\n");
    } else {
        temp = queue->front;
        queue->front = queue->front->next;
        free(temp);
        queue->size--;
        if (queue->front == NULL) {
            /* 特殊处理删除后变为空的队列 */
            queue->rear = NULL;
        }
    }
}

void DestroyQueue(Queue queue) {
    free(queue);
}
/* 链式队列定义结束 */

bool IsVertex(MGraph graph, Vertex v) {
    return (v >= 0 && v < graph->n_verts);
}

bool IsBFS(MGraph graph, Vertex ver[]) {
    Queue queue;
    Vertex u, v, w;
    bool *visited, ret;
    int i;

    /* 初始化辅助工具：访问标识和队列 */
    visited = (bool *)malloc(sizeof(bool) * graph->n_verts);
    for (w = 0; w < graph->n_verts; w++) {
        visited[w] = false;
    }
    queue = (Queue)malloc(sizeof(struct QueueHeadNode));
    InitQueue(queue);
    ret = true; /* 默认返回值为true */
    i = 0; /* i指向ver[]的下一个待访问元素 */
    /* 初始化结束 */
    while (ret == true && i < graph->n_verts) {
        u = ver[i++];
        ret = IsVertex(graph, u);
        if (ret == false)
            break; /* ver中有非法顶点编号 */
        EnQueue(queue, u); /* 起始顶点入列 */
        visited[u] = true;
        while (ret == true && IsEmpty(queue) == false) { /* BFS */
            u = GetFront(queue);
            DeQueue(queue);
            while (i < graph->n_verts) { /* 访问u的所有邻接点v */
                v = ver[i];
                ret = IsVertex(graph, v);
                if (ret == false)
                    break; /* ver中有非法顶点编号 */
                if (visited[v] == true) {
                    ret = false; /* ver中有重复顶点编号 */
                    break;
                } else if (ExistEdge(graph, u, v) == true) {
                    EnQueue(queue, v); /* u的邻接点v入队 */
                    visited[v] = true;
                    i++;
                } else
                    break; /* 遇到第1个不是u的邻接点的v，跳出循环 */
            }
            if (ret == false)
                break;
            else { /* 检查u的邻接点是否都已经被访问 */
                for (w = 0; w < graph->n_verts; w++) {
                    if (ExistEdge(graph, u, w) == true && visited[w] == false) {
                        ret = false; /* 发现ver序列中漏掉了u的邻接点 */
                        break;
                    }
                }
            }
        } /* 完成一个连通分量的BFS */
    }
    DestroyQueue(queue);
    free(visited);
    return ret; /* 若扫描完ver都没有遇到错误，返回默认的true */
}